/**
 * 1. 思路
 * 插入排序的核心思想就是：当前元素前面的序列是有序的，基于这个，当前元素从往前寻找序列里的正确位置
 * 2. 复杂度
 * 最好时间复杂度： 取决于外层循环，内存循环只走一次，为On
 * 最坏时间复杂度： 数组完全逆序，内层循环需要移动有序序列中的所有元素，为On^2
 * 平均时间复杂度：On^2
 */

function insertSort(arr) {
  // 缓存数组长度
  const len = arr.length;
  // temp 用来保存当前需要插入的元素
  let temp;
  // i用于标识每次被插入的元素的索引
  for (let i = 1; i < len; i++) {
    // j用于帮助 temp 寻找自己应该有的定位
    let j = i;
    temp = arr[i];
    // 判断 j 前面一个元素是否比 temp 大
    while (j > 0 && arr[j - 1] > temp) {
      // 如果是，则将 j 前面的一个元素后移一位，为 temp 让出位置
      arr[j] = arr[j - 1];
      j--;
    }
    // 循环让位，最后得到的 j 就是 temp 的正确索引
    arr[j] = temp;
  }
  return arr;
}
